package org.leetcode.middle.leetcode53;

import java.util.Arrays;
import java.util.Map;

public class Solution
{

    public int maxSubArray5(int[]nums){
        int n = nums.length;
        int [] dp = new int[n];

        dp[0]=nums[0];
        int maxSum = Math.max(dp[0],Integer.MIN_VALUE);


        for (int i = 1; i < n; i++) {
            if (dp[i-1]>0){
                dp[i]=dp[i-1]+nums[i];
            }else {
                dp[i]=nums[i];
            }
            maxSum=Math.max(maxSum,dp[i]);
        }

        return maxSum;
    }

    public int maxSubArray4(int[]nums){
        int max =nums[0];
        int n = nums.length;
        int [] dp = new int[n];
        dp[0]=nums[0];

        for (int i = 1; i <n; i++) {
            if (dp[i-1]<0){
                dp[i]=nums[i];
            }else {
                dp[i]=dp[i-1]+nums[i];
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }

    public int maxSubArray3(int[]nums){

        int [] dp = new int [nums.length];

        int max =dp[0]=nums[0];

        for (int i = 1; i <nums.length; i++) {
           if (dp[i-1]>0)
           {
               dp[i]=dp[i-1]+nums[i];
           }else {
               dp[i]=nums[i];
           }

           max=Math.max(dp[i],max);
        }

        return max;
    }


    public int maxSubArray2(int[]nums)
    {
//        Arrays.sort(nums);
//
//        int left =0,right = nums.length-1;
//
//        while (left<=right)
//        {
//
//        }

        return 2;
    }
    public int maxSubArray(int[] nums) {

        int length = nums.length;
        int [] preSums = new int[length+1];

        preSums[0]=0;
        for (int i = 0; i < length; i++) {
            preSums[i+1]=preSums[i]+nums[i];
        }

        int maxNum=0;

        for (int num:preSums) {
            maxNum=Math.max(num,maxNum);
        }


        return maxNum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int [] test = {-2,1,-3,4,-1,2,1,-5,4};
        int i = solution.maxSubArray3(test);
        System.out.println(i);
    }
}
